An important problem that arises in different areas of science andengineering is that of computing the limits of sequences of vectors$\{\xx_m\}$, where $\xx_m\in \C^N$, $N$ being very large. Such sequences arise,for example, in the solution of systems of linear or nonlinear equations byfixed-point iterative methods, and $\lim_{m\to\infty}\xx_m$ are simply therequired solutions. In most cases of interest, however, these sequencesconverge to their limits extremely slowly. One practical way to make thesequences $\{\xx_m\}$ converge more quickly is to apply to them vectorextrapolation methods. Two types of methods exist in the literature: polynomialtype methods and epsilon algorithms. In most applications, the polynomial typemethods have proved to be superior convergence accelerators. Three polynomialtype methods are known, and these are the {minimal polynomial extrapolation}(MPE), the {reduced rank extrapolation} (RRE), and the {modified minimalpolynomial extrapolation} (MMPE). In this work, we develop yet anotherpolynomial type method, which is based on the singular value decomposition, aswell as the ideas that lead to MPE. We denote this new method by SVD-MPE. Wealso design a numerically stable algorithm for its implementation, whosecomputational cost and storage requirements are minimal. Finally, we illustratethe use of {SVD-MPE} with numerical examples.
展开▼
机译:在科学和工程学的不同领域中出现的一个重要问题是计算向量序列的极限$ \ {\ xx_m \} $,其中$ \ xx_m \ in \ C ^ N $,$ N $非常大。这样的序列出现在,例如,通过不动点迭代方法在线性或非线性方程组的解中,而$ \ lim_ {m \ to \ infty} \ xx_m $只是简单的求解答。然而,在大多数感兴趣的情况下,这些序列非常缓慢地收敛到其极限。使这些序列$ \ {\ xx_m \} $更快收敛的一种实用方法是对其应用矢量外推方法。文献中存在两种类型的方法:多项式方法和epsilon算法。在大多数应用中,多项式方法已被证明是卓越的收敛加速器。已知三种多项式类型的方法,它们是{最小多项式外推}(MPE),{降阶外推}(RRE)和{修改的最小多项式外推}(MMPE)。在这项工作中,我们开发了另一种基于奇异值分解的多项式方法以及导致MPE的思想。我们用SVD-MPE表示这种新方法。我们还为其实现设计了数值稳定的算法,其计算成本和存储要求最小。最后,我们通过数值示例说明了{SVD-MPE}的用法。
展开▼